Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Local community detection algorithm based on Monte-Carlo iterative solving strategy
LI Zhanli, LI Ying, LUO Xiangyu, LUO Yingxiao
Journal of Computer Applications    2023, 43 (1): 104-110.   DOI: 10.11772/j.issn.1001-9081.2021111942
Abstract224)   HTML10)    PDF (1690KB)(97)       Save
Aiming at the problems of premature convergence and low recall caused by using greedy strategy for community expansion in the existing local community detection algorithms, a local community detection algorithm based on Monte-Carlo iterative solving strategy was proposed. Firstly, in the community expansion stage of each iteration, the selection probabilities were given to all adjacent candidate nodes according to the contribution ratio of each node to the community tightness gain, and one node was randomly selected to join the community according to these probabilities. Then, in order to avoid random selection causing the expansion direction to deviate from the target community, it was determined whether the node elimination mechanism was triggered in this round of iteration according to the changes in community quality. If it was triggered, the similarity sum of each node joining the community and other nodes in the community was calculated, the elimination probabilities were assigned according to the reciprocal of the similarity sum, a node was randomly eliminated according to these probabilities. Finally, whether to continue the iteration was judged on the basis of whether the community size increased in a given number of recent iteration rounds. Experimental results show that, on three real network datasets, compared to Local Tightness Expansion (LTE) algorithm, Clauset algorithm, Common Neighbors with Weighted Neighbor Nodes (CNWNN) algorithm and Fuzzy Similarity Relation (FSR) algorithm, the proposed algorithm has the F-score value of local community detection results increased by 32.75 percentage points, 17.31 percentage points, 20.66 percentage points and 25.51 percentage points respectively, and can effectively avoid the influence of the location of the query node in the community on the local community detection results.
Reference | Related Articles | Metrics